package 剑指offer.zw_10I_斐波那契数列;

class Solution {
    public static void main(String[] args) {
        int n = 44;
        int num = fib(n);
        System.out.println(num);

    }

    public static int fib(int n) {
        final int MOD = 1000000007;
        if (n < 2) {
            return n;
        }
        int p = 0, q = 0, r = 1;
        for (int i = 2; i <= n; ++i) {
            p = q;
            q = r;
            r = (p + q) % MOD;
        }
        return r;
    }


    /**
     * 递归
     *
     * @param n
     * @return
     */
//    public static int fib(int n) {
//        return f(n);
//    }
//
//    public static int f(int n) {
//        if (n <= 1) return n;
//        return f(n - 1) + f(n - 2);
//    }
}
